//
// Description: 416. 分割等和子集
// Created by Loading on 2022/4/10.
//

#include <bits/stdc++.h>

using namespace std;

bool canPartition(vector<int> &nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    int mx = *max_element(nums.begin(), nums.end());
    // 数组总和为奇数，不可能分割成功
    if (sum % 2) {
        return false;
    }
    sum /= 2;
    int n = nums.size();
    // 元素数量少于两个或最大值大于总和的一半，不可能分割成功
    if (n < 2 || mx > sum) {
        return false;
    }

    /* 0-1背包 */
    // 一维dp，空间优化，dp[i]表示是否可以组成和为i
    vector<bool> dp(sum + 1);
    dp[0] = true;
    for (int i = 0; i < n; ++i) {
        /* 逆序遍历 */
        for (int j = sum; j >= nums[i]; --j) {
            dp[j] = dp[j] | dp[j - nums[i]];
        }
    }

    return dp[sum];
}

int main() {
    vector<int> nums{1, 5, 11, 5};
    auto res = canPartition(nums);
    cout << res << endl;

    return 0;
}